package com.adee.algorithm.structure;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;

/*
* 链表相关
* */
public class Test002_List {
    public static void main(String[] args) {
//         test1();
//        test1_2();
//         test2();
         test3();
//        test4();
    }

    // 查找一个单链表的倒数第k个节点（新浪面试题）
    public static void test1() {
        Node<Integer> head = newSingleList(12);
        System.out.println("链表：");
        printList(head);
        System.out.println(getRk1(head,0));
        System.out.println(getRk1(head,1));
        System.out.println(getRk1(head,2));
        System.out.println(getRk1(head,8));
        System.out.println(getRk1(head,9));
        System.out.println(getRk1(head,12));
        System.out.println("----- ");
        System.out.println(getRk2(head,0));
        System.out.println(getRk2(head,1));
        System.out.println(getRk2(head,2));
        System.out.println(getRk2(head,8));
        System.out.println(getRk2(head,9));
        System.out.println(getRk2(head,12));
    }
    // 测试两种算法的速度，结果：第一种更快
    public static void test1_2() {
        int n = 50000000;
        Node<Integer> head = newSingleList(n);
        long t1 = System.currentTimeMillis();
        getRk1(head,0);
        long t2 = System.currentTimeMillis();
        getRk2(head,0);
        long t3 = System.currentTimeMillis();
        System.out.println("getRk1耗时：" + (t2-t1)); // 268
        System.out.println("getRk2耗时：" + (t3-t2)); // 1229 性能损耗在数组元素索引赋值和扩容
    }

    /*
     * 查找一个单链表的倒数第k个节点（新浪面试题）
     * 注：倒数第0个，即为正数第len-1个。
     *    倒数第1个，即为正数第(len-1)-1个
     *    倒数第k个，即为正数第(len-1-k)个
     * 两种算法：
     * 1.两次遍历：先遍历链表得出len的值，然后再遍历找到第len-1-k个元素；
     * 2.一次遍历：先遍历链表得出len的值，遍历的同时将链表元素索引到一个临时数组arr上，然后直接返回arr[len-1-k]即可。
     * 两种算法的时间复杂度都是n。
     * 两种算法测试比较结果：第1种更快，因为第2种多了数组索引赋值的操作。
     * 线程不安全
     * */
    public static Node<Integer> getRk1(Node<Integer> head, int k) {
        // 参数校验
        if(head == null || k < 0) {
            throw new IllegalArgumentException("head == null || k < 0");
        }
        // 计算len
        int len = 0;
        for(Node<Integer> temp = head; temp != null; temp = temp.next) {
            len++;
        }
        // 倒数第k个，即为正数第len-1-k
        if(k > len - 1) {
            throw new RuntimeException("k超出链表长度" + len);
        }
        // i为temp的索引，保持同步
        int i = 0;
        int dest = len - 1 - k;
        for(Node<Integer> temp = head; temp != null; temp = temp.next) {
            if(i++ == dest) {
                return temp;
            }
        }
        return null;
    }

    public static Node<Integer> getRk2(Node<Integer> head, int k) {
        // 参数校验
        if(head == null || k < 0) {
            throw new IllegalArgumentException("head == null || k < 0");
        }
        // 临时数组，用于线性索引链表元素，初始长度8，不够再扩容
        Node<Integer>[] arr = new Node[50*1024*1024]; // 50M
        // 计算len
        int len = 0;
        for(Node<Integer> temp = head; temp != null; temp = temp.next) {
            if(len+1 > arr.length) {
                // 扩容
                Node<Integer>[] arrNew = new Node[arr.length*2];
                System.arraycopy(arr, 0, arrNew, 0, arr.length);
                arr = arrNew;
            }
            arr[len] = temp;
            len++;
        }
        // 倒数第k个，即为正数第len-1-k
        if(k > len - 1) {
            throw new RuntimeException("k超出链表长度" + len);
        }
        return arr[len-1-k];
    }

    /*
    * 单链表的反转（腾讯面试题）
    * */
    public static void test2() {
        Node<Integer> head = newSingleList(9);
        System.out.println("原始链表：");
        printList(head);
        Node<Integer> reverse = reverse(head);
        System.out.println("使用栈方式反转后链表：");
        printList(reverse);
        Node<Integer> reverse2 = reverse2(reverse);
        System.out.println("使用原生数组方式反转后链表：");
        printList(reverse2);
    }

    /*
     * 单链表的反转（腾讯面试题）
     * 使用栈实现
     * */
    public static Node<Integer> reverse(Node<Integer> head) {
        Stack<Node> stack = new Stack<>();
        while(head != null) {
            stack.push(head);
            head = head.next;
        }
        Node<Integer> newHead = null;
        Node<Integer> newTail = null;
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            if(newHead == null)
                newHead = newTail = node;
            else {
                newTail.next = node;
                newTail = node;
            }
        }
        newTail.next = null; // 别忘给尾节点的next置空
        return newHead;
    }
    // 不使用包装类Stack，使用原生数组实现
    public static Node<Integer> reverse2(Node<Integer> head) {
        if (head == null) return null;
        Node<Integer>[] arr = new Node[16];
        int i = 0;
        for (Node<Integer> temp = head; temp != null; temp = temp.next) {
            if(i+1 > arr.length) {
                // 扩容
                Node<Integer>[] arrNew = new Node[arr.length*2];
                System.arraycopy(arr, 0, arrNew, 0, arr.length);
                arr = arrNew;
            }
            arr[i++] = temp;
        }
        i--;
        // 此时i为最后一个元素的下标
        for (int j = i; j > 0; j--) {
            arr[j].next = arr[j-1];
        }
        arr[0].next = null;

        return arr[i];
    }

    // 合并两个有序链表
    public static void test3() {
        Node<Integer> head1 = newOrderedSingleList(10);
        System.out.println("有序链表1：");
        printList(head1);
        Node<Integer> head2 = newOrderedSingleList(6);
        System.out.println("有序链表2：");
        printList(head2);
        Node<Integer> head3 = merge(head1, head2);
        System.out.println("合并后链表：");
        printList(head3);
    }

    /*
     * 合并两个有序链表
     * */
    public static Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) {
        if(head1 == null) return head2;
        if(head2 == null) return head1;

        Node<Integer> cur = null;
        Node<Integer> other = null;
        Node<Integer> tmp = null;
        int c = head2.compareTo(head1);
        cur = c > 0 ? head1 : head2;
        other = c > 0 ? head2 : head1;
        Node<Integer> retHead = cur;
        while(true) {
            // cur < other
            if(other == null) break;
            // if(cur == null) {} // cur为上一步的cur.next或other，不可能为null
            if(cur.next == null) {
                cur.next = other;
                break;
            }
            // cur.next和other比较
            if(cur.next.compareTo(other) > 0) {
                tmp = cur.next;
                cur.next = other;
                other = tmp;
            } else {
                cur = cur.next;
            }
        }
        return retHead;
    }

    static Node<Integer> max(Node<Integer> a, Node<Integer> b) {
        return a.compareTo(b) > 0 ? a : b;
    }



    // 约瑟夫环问题
    public static void test4() {
        Node<Integer>[] arr = newRingSingleList(10);
        System.out.println("约瑟夫环：");
        printRingList(arr[0]);
        List<Integer> list = josephu(arr, 3, 2);
        System.out.println("输出：");
        System.out.println(list);
    }
    /*
    * 循环链表解决约瑟夫环问题
    * 约瑟夫环问题：
    *   设编号为1，2，...，n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人
    *   出列，他的下一位又从1开始报数，数到m的人又出列，依此类推，直到所有人都出列，由此产生一个出队编号的序列。
    * */
    public static List<Integer> josephu(Node<Integer>[] arr, int k, int m) {
        List<Integer> list = new ArrayList<>();
        Node<Integer> head = arr[0];
        Node<Integer> tail = arr[1];
        Node<Integer> curr = head;
        Node<Integer> prev = tail;
        // curr指向第k个人
        for (int i = 1; ; i++) {
            if(i == k) break;
            curr = curr.next;
            prev = prev.next;
        }
        for (int i = 1; curr != null; i++) {
            if(i == m) { // 数到的人出队
                list.add(curr.value);
                if(curr == curr.next) { // 只剩1个元素
                    break;
                } else {
                    prev.next = curr.next;
                    curr = curr.next;
                    i = 0;
                    continue;
                }
            }
            curr = curr.next;
            prev = prev.next;
        }
        return list;
    }

    // 创建一个普通单链表
    public static Node<Integer> newSingleList(int n) {
        ThreadLocalRandom r = ThreadLocalRandom.current();
        Node<Integer> head = new Node<>(r.nextInt(100));
        Node<Integer> tail = head;
        for (int i = 0; i < n; i++) {
            tail = tail.setNext(new Node<>(r.nextInt(100)));
        }
        return head;
    }

    // 创建一个循环单链表
    public static Node<Integer>[] newRingSingleList(int n) {
        ThreadLocalRandom r = ThreadLocalRandom.current();
        Node<Integer> head = new Node<>(r.nextInt(100));
        Node<Integer> tail = head;
        for (int i = 0; i < n; i++) {
            tail = tail.setNext(new Node<>(r.nextInt(100)));
        }
        tail.setNext(head);
        return new Node[]{head, tail};
    }

    // 创建一个有序单链表
    public static Node<Integer> newOrderedSingleList(int n) {
        ThreadLocalRandom r = ThreadLocalRandom.current();
        Node<Integer> head = new Node<>(r.nextInt(100));
        for (int i = 0; i < n; i++) {
            Node<Integer> newNode = new Node<>(r.nextInt(100));
            if(newNode.compareTo(head) <= 0) {
                newNode.next = head;
                head = newNode;
                continue;
            }
            Node<Integer> curr = head;
            // 从小到大
            while(curr != null) {
                int compare = newNode.compareTo(curr);
                if(newNode.compareTo(curr) > 0) {
                    if (curr.next == null) {
                        curr.next = newNode;
                        break;
                    } else if (newNode.compareTo(curr.next) <= 0) {
                        newNode.next = curr.next;
                        curr.next = newNode;
                        break;
                    } else {
                        curr = curr.next;
                    }
                }
            }
        }
        return head;
    }

    public static void printList(Node head) {
        while(head != null){
            System.out.print(head.value + "\t");
            head = head.next;
        }
        System.out.println();
    }

    public static void printRingList(Node head) {
        Node curr = head;
        do{
            System.out.print(curr.value + "\t");
            curr = curr.next;
        }while(curr != head);
        System.out.println();
    }

    // 单链表节点
    static class Node<V> implements Comparable<Node>{
        V value;
        Node<V> next;
        public Node(V e) {
            value = e;
        }
        Node<V> setNext(Node<V> n) {
            next = n;
            return n;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return (Integer)value - (Integer)o.value;
        }
    }
}
